package 面试;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 出现频率最多的 k 个数
 */
public class TOPK2 {
    /**
     * 使用桶排序
     * <p>
     * 设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率，即第 i 个桶中存储的数出现的频率为 i。
     * <p>
     * 把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
     */
    // Given [1,1,1,2,2,3] and k = 2, return [1,2].
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        // 设置若干个桶。出现频率相同的元素放到同一个桶里面。然后以频率作为桶下标
        for (int key : map.keySet()) {
            int frequency = map.get(key);
            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }
            buckets[frequency].add(key);
        }
        // 从后往前遍历，取出 k 个元素
        List<Integer> topK = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
            if (buckets[i] == null) {
                continue;
            }
//            if (buckets[i].size() <= (k - topK.size())) {
//                topK.addAll(buckets[i]);
//            } else {
//                topK.addAll(buckets[i].subList(0, k - topK.size()));
//            }

            topK.addAll(buckets[i]);
        }
        return topK;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        List<Integer> list = topKFrequent(nums, k);
        list.forEach((e) -> System.out.print(e + " "));
    }

}
